package com.example.shortestpathalgorithm44;

import java.util.LinkedList;


/**
 * 单源最短路径算法
 * @auther lijiewei
 * @date 2022/7/12 16:50
 */
public class DijkstraAlgorithm {


    /**
     * 从顶点s到顶点t的最短路径
     * @param s 顶点s
     * @param t 顶点t
     * @return
     * @author lijiewei
     * @date   2022/7/13 11:43
     */
    public void dijkstra(Graph graph, int s, int t) {
        LinkedList<Graph.Edge>[] adj = graph.getAdj();
        int count = graph.getV();

        //用来还原最短路径,值存储起点(指向当前节点)的下标
        int[] predecessor = new int[count];
        Node[] nodes = new Node[count];
        for (int i = 0; i < count; i++) {
            nodes[i] = new Node(i, Integer.MAX_VALUE);
        }

        //小顶堆
        PriorityQueue queue = new PriorityQueue(count);
        //标记是否进入过队列
        boolean[] inqueue = new boolean[count];
        nodes[s].setDist(0);
        queue.add(nodes[s]);
        inqueue[s] = true;

        while (!queue.isEmpty()) {
            //取堆顶元素并删除
            Node minNode = queue.poll();
            //最短路径产品了
            if (minNode.getId() == t) {
                break;
            }

            for (int i = 0; i < adj[minNode.getId()].size(); i++) {
                //取出一条minNode相连的边
                Graph.Edge edge = adj[minNode.getId()].get(i);
                //minNode --> nextNode
                Node nextNode = nodes[edge.tid];
                if (minNode.getDist() + edge.w < nextNode.getDist()) {
                    nextNode.setDist(minNode.getDist()+edge.w);
                    predecessor[nextNode.getId()] = minNode.getId();

                    if (inqueue[nextNode.getId()]) {
                        //更新队列中的dist值
                        queue.update(nextNode);
                    } else {
                        queue.add(nextNode);
                        inqueue[nextNode.getId()] = true;
                    }

                }
            }
        }
        //输出最短路径
        System.out.print(s);
        print(s, t, predecessor);
        System.out.println();
    }

    private void print(int s, int t, int[] predecessor) {
        if (s == t) {
            return;
        }
        print(s, predecessor[t], predecessor);
        System.out.print(" -> " +t);
    }

}
